88. 合并两个有序数组

Similar Question

leading to the advanced question

Solution Tips

方案一: 直接排序后合并

var merge = function(nums1, m, nums2, n) {
    nums1.splice(m, nums1.length - m, ...nums2);
    nums1.sort((a, b) => a - b);
};

方案二: 双指针 + 额外数组

方法一没有利用数组 nums 1 ​ 与 nums 2 ​ 已经被排序的性质。为了利用这一性质，我们可以使用双指针方法。这一方法将两个数组看作队列，每次从两个数组头部取出比较小的数字放到结果中。如下面的动画所示：

var merge = function(nums1, m, nums2, n) {
    let p1 = 0, p2 = 0;
    const sorted = new Array(m + n).fill(0);
    var cur;
    while (p1 < m || p2 < n) {
        if (p1 === m) {
            cur = nums2[p2++];
        } else if (p2 === n) {
            cur = nums1[p1++];
        } else if (nums1[p1] < nums2[p2]) {
            cur = nums1[p1++];
        } else {
            cur = nums2[p2++];
        }
        sorted[p1 + p2 - 1] = cur;
    }
    for (let i = 0; i != m + n; ++i) {
        nums1[i] = sorted[i];
    }
}

方案三: 尾插法 逆向双指针

var merge = function(nums1, m, nums2, n) {
    // 倒过来 merge 就不怕覆盖了? 确实, 极端情况就是 n 直接覆盖完所有的 0
    // m 不用变动, 也不怕被覆盖
    let cur = nums1.length - 1;
    let i = m - 1;
    let j = n - 1;

    while (i >= 0 || j >= 0) {
        // 负数索引为 undefined, 需要视为最小值
        const a = nums1[i] ?? Number.MIN_SAFE_INTEGER;
        const b = nums2[j] ?? Number.MIN_SAFE_INTEGER;
        if (a >= b) {
            nums1[cur] = nums1[i];
            cur--;
            i--;
        }
        else {
            nums1[cur] = nums2[j]
            cur--;
            j--;
        }
    }

    return nums1;
};